Greedy Algorithm: What is the Greedy Algorithm? A Case Study on the Coin Change Problem

Greedy algorithm is an algorithm that makes the optimal choice (local optimum) at each step in the hope of achieving a global optimum. Its core is to satisfy the "greedy choice property"—that the local optimum at each step can lead to the global optimum. A classic application is the coin change problem: taking 25, 10, 5, and 1-cent coins as examples, to make 67 cents, we take 25×2 (50 cents), 10×1 (10 cents), 5×1 (5 cents), and 1×2 (2 cents) in descending order of denominations, totaling 6 coins, which is verified as optimal. However, its limitation is that if the problem does not satisfy the greedy choice property (e.g., with coin denominations [1, 3, 4] to make 6 cents), the greedy approach may fail (greedy would take 4+1+1=3 coins, while the optimal is 3+3=2 coins). Applicable scenarios include reasonable coin denominations (e.g., 25, 10, 5, 1) and activity scheduling (selecting the earliest-ending activities). In conclusion, the greedy algorithm is simple, intuitive, and efficient, but it only applies to problems that satisfy the greedy choice property and does not guarantee the global optimum for all problems.